# 缺失的第一个正数： https://leetcode-cn.com/problems/first-missing-positive/submissions/

# 直接模拟过程，先排序，然后再对排序后的数组进行判断缺哪个
class Solution:
    def firstMissingPositive(self, nums: list) -> int:
        """
            解出来就行，先尝试
        """
        nums.sort()

        i = 0
        # 1. 找到第一个正整数，看他是否 为1
        while i < len(nums) and nums[i] < 1:
            i += 1
        
        # 2. 如果最后一个位置还小于0 或者 第一个整数不是1，返回1
        if i >= len(nums) or nums[i] != 1: return 1 
        
        # 3. 如果第一个正整数为1，判断中间位置到最后是否有空缺数字
        while i < len(nums) - 1:
            # 如果有重复出现的数字，就跳过去
            if nums[i] == nums[i + 1]: 
                i += 1
                continue
            # 判断是否连续
            if nums[i] + 1 != nums[i + 1]:
                return nums[i] + 1
            
            i += 1

            """
            优化if语句写法
            if nums[i] != nums[i + 1] and nums[i] + 1 != nums[i + 1]: 
                return nums[i] + 1
            i += 1
            """

        # 4. 如果没有空缺位置，那就返回最后位置的值 + 1， 注意要大于0， 所以和 1比较（其实有了第一个while判断这里不需要和1比较了）
        return max(nums[-1] + 1, 1)

        
# 解法二
class Solution:
    def firstMissingPositive(self, nums: list) -> int:
        """
            hash查找的暴力解法：
            题目的意思就是最小从1开始，一直往后寻找缺失的整数，一种暴力的顺序查找就是，逐个遍历1 -> n + 1 寻找在列表中是否存在.(因为列表长度是 n， 最大元素也就是 1 - n)
            优化下就是，将线性的在列表中查找，优化为在hash表中查找，将列表元素移至hash表
            创建集合 O(n) , 查找缺失的值，因为小的缺失必然得出结果，最坏情况下最后一位缺失，时间复杂度是O(n)
            空间复杂度是 O(n)
        """
        
        n = len(nums)
        
        # 将元素移动至 set类型中
        setNums = set(nums)

        # 循环查找缺失的值：
        for num in range(1, n + 2):
            if num not in setNums:
                return num


# 解法三，再次思考， 优化空间，去掉集合类型
class Solution:
    def firstMissingPositive(self, nums: list) -> int:
        """
            根据hash查找的暴力解法： 会占用额外的存储空间，创建集合。那么既然是使用hash类型， 并且观察到数组长度为n的话，对应的元素理应为 1 -> n , 
            那么数组的下标和元素值相等，又可以利用这个特点（有这种特点，都该往这里想），将原始列表添加标记，构造为简单的标记，hash
            有两种标记的方法， 一种是 * -1 负数标记， 另外是 + n  取模标记，这里适合使用第一种
        """
        
        n = len(nums)

        # 1. 首先可以将 小于0的元素 变为 n + 1
        for i in range(n):
            if nums[i] <= 0: nums[i] = n + 1
        
        # 2. 再次遍历， 指定 1 -- n 的整数，对应的下标变为 负数
        for i in range(n):
            absNum = abs(nums[i]) 
            # 这里需要加上判断 nums[absNum - 1] < 0， 比如[1,1]， 当元素重复出现两次的时候， 负负得正了
            if 1 <= absNum and absNum <= n and nums[absNum - 1] > 0: 
                nums[absNum - 1] *= -1
        
        # 3. 因为符合要求的元素都已经标记到指定的下标，那么再次遍历，第一个 位置大于0的，就是缺失元素的位置
        for i in range(n):
            if nums[i] > 0:
                return i + 1

        # 4. 都不缺的话，就是末尾返回 n + 1
        return n + 1

# 再次优化，交换
class Solution:
    def firstMissingPositive(self, nums: list) -> int:
        """
            根据上面的标记法，再次优化！， 因为就是为了得到对应的 标记后的列表来判断是否缺失元素，
            那么可以直接进行交换操作，将每个元素都放到正确的位置，再次判断缺失谁。比如：
            [3, 1, 0]  正确位置为  [1, 0, 3],  每个元素放到自己对应的下标， 那么缺失谁就很明显了
            一次交换一个元素回到正确位置，所 以时间复杂度还是 O(n)
        """    
        n = len(nums)

        # 1. 进行交换, 需要注意的是， 交换后不能立即 i++ 比较下一个数，要进行判断，交换到当前位置的数，还能不能继续换
        """ 举例子
            [3,4,-1,1]，  第一次 [-1 4 3 1]  第二次[-1 1 3 4] 会发现 1没有被进行置换，所以需要循环判断
            但是循环判断又会出问题了！ nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i] 很可能出现死循环来回替换
            举例子
            [1 2 0]  1就是在当前位置， 或者 [1, 1] 会出现无限制的死循环，把1往当前位置替换，需要 nums[i] != nums[nums[i] - 1] 来进行判断, 交换位置的元素不等于当前位置的元素
        """
        for i in range(n):
            # 一直判断，交换到当前位置的值，是否还需要继续进行交换， 当前元素就是指定位置时，不进行替换了
            while nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                t = nums[i] - 1
                nums[i], nums[t] = nums[t], nums[i]
        
        print(nums)

        # 2. 进行判断缺失谁
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1   

        # 3.
        return n + 1

# nums = [3,4,-1,1]
nums = [1, 1]

s = Solution()
rst = s.firstMissingPositive(nums)
print(rst)